home *** CD-ROM | disk | FTP | other *** search
/ Danny Amor's Online Library / Danny Amor's Online Library - Volume 1.iso / html / rfc / rfcxxxx / rfc1164 < prev    next >
Text File  |  1995-07-25  |  55KB  |  1,291 lines

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group              J. Honig, Cornell Univ. Theory Center
  8. Request for Comments: 1164                         D. Katz, Merit/NSFNET
  9.                              M. Mathis, Pittsburgh Supercomputing Center
  10.                        Y. Rekhter, T.J. Watson Research Center, IBM Corp
  11.                                                      J. Yu, Merit/NSFNET
  12.                                                                June 1990
  13.  
  14.        Application of the Border Gateway Protocol in the Internet
  15.  
  16. Status of this Memo
  17.  
  18.    This RFC, together with its companion RFC-1163, "A Border Gateway
  19.    Protocol (BGP)", define a Proposed Standard for an inter-autonomous
  20.    system routing protocol for the Internet.
  21.  
  22.    This protocol, like any other at this initial stage, may undergo
  23.    modifications before reaching full Internet Standard status as a
  24.    result of deployment experience.  Implementers are encouraged to
  25.    track the progress of this or any protocol as it moves through the
  26.    standardization process, and to report their own experience with the
  27.    protocol.
  28.  
  29.    This protocol is being considered by the Interconnectivity Working
  30.    Group (IWG) of the Internet Engineering Task Force (IETF).
  31.    Information about the progress of BGP can be monitored and/or
  32.    reported on the IWG mailing list (IWG@nri.reston.va.us).
  33.  
  34.    Please refer to the latest edition of the "IAB Official Protocol
  35.    Standards" RFC for current information on the state and status of
  36.    standard Internet protocols.
  37.  
  38.    Distribution of this memo is unlimited.
  39.  
  40. Table of Contents
  41.  
  42.    1. Acknowledgements.......................................    2
  43.    2. Introduction...........................................    2
  44.    3. BGP Theory and Application.............................    3
  45.    3.1 Topological Model.....................................    3
  46.    3.2 BGP in the Internet...................................    4
  47.    3.2.1 Topology Considerations.............................    4
  48.    3.2.2 Global Nature of BGP................................    5
  49.    3.2.3 BGP Neighbor Relationships..........................    5
  50.    3.3 Policy Making with BGP................................    6
  51.    4. Operational Issues.....................................    7
  52.    4.1 Path Selection........................................    7
  53.    4.2 Syntax and Semantics for BGP Configuration Files......    9
  54.    5. The Interaction of BGP and an IGP......................   17
  55.  
  56.  
  57.  
  58. Interconnectivity Working Group                                 [Page 1]
  59.  
  60. RFC 1164                   BGP - Application                   June 1990
  61.  
  62.  
  63.    5.1 Overview..............................................   17
  64.    5.2 Methods for Achieving Stable Interactions.............   17
  65.    5.2.1 Propagation of BGP Information via the IGP..........   18
  66.    5.2.2 Tagged Interior Gateway Protocol....................   18
  67.    5.2.3 Encapsulation.......................................   19
  68.    5.2.4 Other Cases.........................................   19
  69.    6. Implementation Recommendations.........................   20
  70.    6.1 Multiple Networks Per Message.........................   20
  71.    6.2 Preventing Excessive Resource Utilization.............   20
  72.    6.3 Processing Messages on a Stream Protocol..............   21
  73.    6.4 Processing Update Messages............................   21
  74.    7. Conclusion.............................................   22
  75.    References................................................   22
  76.    Security Considerations...................................   22
  77.    Authors' Addresses........................................   22
  78.  
  79. 1. Acknowledgements
  80.  
  81.    The authors would like to thank Guy Almes (Rice University), Kirk
  82.    Lougheed (cisco Systems), Hans-Werner Braun (Merit/NSFNET), Sue Hares
  83.    (Merit/NSFNET), and the Interconnectivity Working Group of the
  84.    Internet Engineering Task Force (chaired by Guy Almes) for their
  85.    contributions to this paper.
  86.  
  87. 2. Introduction
  88.  
  89.    The Border Gateway Protocol (BGP), described in RFC 1163, is an
  90.    interdomain routing protocol.  The network reachability information
  91.    exchanged via BGP provides sufficient information to detect routing
  92.    loops and enforce routing decisions based on performance preference
  93.    and policy constraints as outlined in RFC 1104 [2].
  94.  
  95.    This memo uses the term "Autonomous System" throughout.  The classic
  96.    definition of an Autonomous System is a set of routers under a single
  97.    technical administration, using an interior gateway protocol and
  98.    common metrics to route packets within the AS, and using an exterior
  99.    gateway protocol to route packets to other ASs.  Since this classic
  100.    definition was developed, it has become common for a single AS to use
  101.    several interior gateway protocols and sometimes several sets of
  102.    metrics within an AS.  The use of the term Autonomous System here
  103.    stresses the fact that, even when multiple IGPs and metrics are used,
  104.    the administration of an AS appears to other ASs to have a single
  105.    coherent interior routing plan and presents a consistent picture of
  106.    what networks are reachable through it.  From the standpoint of
  107.    exterior routing, an AS can be viewed as monolithic: reachability to
  108.    networks directly connected to the AS must be equivalent from all
  109.    border gateways of the AS.
  110.  
  111.  
  112.  
  113.  
  114. Interconnectivity Working Group                                 [Page 2]
  115.  
  116. RFC 1164                   BGP - Application                   June 1990
  117.  
  118.  
  119.    This paper discusses the use of BGP in the Internet environment.
  120.    Issues such as topology, the interaction between BGP and IGPs, and
  121.    the enforcement of policy rules with BGP will be presented.
  122.  
  123.    All of the discussions in this paper are based on the assumption that
  124.    the Internet is a collection of arbitrarily connected Autonomous
  125.    Systems.  The AS is assumed to be administered by a single
  126.    administrative entity, at least for the purposes of representation of
  127.    routing information to systems outside of the AS.
  128.  
  129. 3. BGP Theory and Application
  130.  
  131. 3.1 Topological Model
  132.  
  133.    We will be concerned throughout this paper with a general graph whose
  134.    nodes are ASs and whose edges are connections between pairs of ASs.
  135.    The notion of AS is discussed above in Section 2.  When we say that a
  136.    connection exists between two ASs, we mean both of two things:
  137.  
  138.    physical connection: there is a shared network between the two ASs,
  139.       and on this shared network each AS has at least one border gateway
  140.       belonging to that AS.  Thus the border gateway of each AS can
  141.       forward packets to the border gateway of the other AS without
  142.       resort to Inter-AS or Intra-AS routing.
  143.  
  144.    BGP connection: there is a BGP session between BGP speakers on each
  145.       of the ASs, and this session communicates to each connected AS
  146.       those routes through the physically connected border gateways of
  147.       the other AS that can be used for specific networks.  Throughout
  148.       this document we place an additional restriction on the BGP
  149.       speakers that form the BGP connection: they must themselves share
  150.       the same network that their border gateways share.  Thus, a BGP
  151.       session between the adjacent ASs requires no support from either
  152.       Inter-AS or Intra-AS routing.  Cases that do not conform to this
  153.       restriction fall outside the scope of this document.
  154.  
  155.    Thus, at each connection, each AS has one or more BGP speakers and
  156.    one or more border gateways, and these BGP speakers and border
  157.    gateways are all located on a shared network.  Only the AS's border
  158.    gateways on the connection's shared network may be used by that AS's
  159.    BGP speakers on that shared network in NEXT_HOP attributes in Update
  160.    messages.  Paths announced by a BGP speaker of one AS on a given
  161.    connection are taken to be feasible for each of the border gateways
  162.    of the other AS on the same connection.  In all BGP usage, we intend
  163.    that the flow of packets from one AS to the other correspond to
  164.    advertised AS paths.
  165.  
  166.    Much of the traffic carried within an AS either originates or
  167.  
  168.  
  169.  
  170. Interconnectivity Working Group                                 [Page 3]
  171.  
  172. RFC 1164                   BGP - Application                   June 1990
  173.  
  174.  
  175.    terminates at that AS (i.e., either the source IP address or the
  176.    destination IP address of the IP packet identifies a host on a
  177.    network directly connected to that AS).  Traffic that fits this
  178.    description is called "local traffic".  Traffic that does not fit
  179.    this description is called "transit traffic".  A major goal of BGP
  180.    usage is to control the flow of transit traffic.
  181.  
  182.    Based on how a particular AS deals with transit traffic, the AS may
  183.    now be placed into one of the following categories:
  184.  
  185.    stub AS: an AS that has only a single connection to another AS.
  186.       Naturally, a stub AS only carries local traffic.
  187.  
  188.    multihomed AS: an AS that has more than one connection to other ASs,
  189.       but refuses to carry transit traffic.
  190.  
  191.    transit AS: an AS that has more than one connection to other ASs and
  192.       is designed (under certain policy restrictions) to carry both
  193.       transit and local traffic.
  194.  
  195.    Since a full AS path provides an efficient and straightforward way of
  196.    suppressing routing loops and eliminates the "count-to-infinity"
  197.    problem associated with some distance vector algorithms, BGP imposes
  198.    no topological restrictions on the interconnection of ASs.
  199.  
  200. 3.2 BGP in the Internet
  201.  
  202. 3.2.1 Topology Considerations
  203.  
  204.    The overall Internet topology may be viewed as an arbitrary
  205.    interconnection of transit, multihomed, and stub ASs.  In order to
  206.    minimize the impact on the current Internet infrastructure, stub and
  207.    multihomed ASs need not use BGP.  These ASs may run other protocols
  208.    (e.g., EGP) to exchange reachability information with transit ASs.
  209.    Transit ASs then tag this information as having been learned via EGP
  210.    or some other method.  The fact that BGP need not run on stub or
  211.    multihomed ASs has no negative impact on the overall quality of
  212.    inter-AS routing for traffic not local to the stub or multihomed ASs
  213.    in question.
  214.  
  215.    Of course, BGP may be used for stub and multihomed ASs as well,
  216.    providing advantage in bandwidth and performance over some of the
  217.    currently used protocols (such as EGP). In addition, this would
  218.    result in less need for the use of defaults and in better choices of
  219.    Inter-AS routes for mulitihomed ASs.
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226. Interconnectivity Working Group                                 [Page 4]
  227.  
  228. RFC 1164                   BGP - Application                   June 1990
  229.  
  230.  
  231. 3.2.2 Global Nature of BGP
  232.  
  233.    At a global level, BGP is used to distribute routing information
  234.    among multiple Autonomous Systems.  The information flows can be
  235.    represented as follows:
  236.  
  237.                           +--------+       +--------+
  238.                     BGP   |  BGP   |  BGP  |  BGP   |  BGP
  239.                   --------+        +-------+        +-------
  240.                           |  IGP   |       |  IGP   |
  241.                           +--------+       +--------+
  242.  
  243.                          {___AS A___}     {___AS B___}
  244.  
  245.    This diagram points out that, while BGP alone carries information
  246.    between ASs, a combination of BGP and an IGP carries information
  247.    across an AS.  Ensuring consistency of routing information between
  248.    BGP and an IGP within an AS is a significant issue and is discussed
  249.    at length later in this paper.
  250.  
  251. 3.2.3 BGP Neighbor Relationships
  252.  
  253.    As discussed in the introduction, the Internet is viewed as a set of
  254.    arbitrarily connected Autonomous Systems (ASs).  BGP gateways in each
  255.    AS communicate with each other to exchange network reachability
  256.    information based on a set of policies established within each AS.
  257.    Computers that communicate directly with each other via BGP are known
  258.    as BGP neighbors.  BGP neighbors can be located within the same AS or
  259.    in different ASs.  For the sake of discussion, BGP communications
  260.    with neighbors in different ASs will be referred to as External BGP,
  261.    and with neighbors in the same AS as Internal BGP.
  262.  
  263.    External BGP In the case of External BGP, the BGP neighbors must
  264.       belong to different ASs, but share a common network.  This common
  265.       network should be used to carry the BGP messages between them.
  266.       The use of BGP across an intervening AS invalidates the AS path
  267.       information.  An Autonomous System number must be used with BGP to
  268.       specify which Autonomous System the BGP speaker belongs to.
  269.  
  270.    Internal BGP There can be as many BGP gateways as deemed necessary
  271.       within an AS.  Usually, if an AS has multiple connections to other
  272.       ASs, multiple BGP gateways are needed.  All BGP gateways
  273.       representing the same AS must give a consistent image of the AS to
  274.       the outside.  This requires that the BGP gateways have consistent
  275.       routing information among them.  These gateways can communicate
  276.       with each other via BGP or by other means.  The policy constraints
  277.       applied to all BGP gateways within an AS must be consistent.
  278.  
  279.  
  280.  
  281.  
  282. Interconnectivity Working Group                                 [Page 5]
  283.  
  284. RFC 1164                   BGP - Application                   June 1990
  285.  
  286.  
  287. 3.3 Policy Making with BGP
  288.  
  289.    BGP provides the capability of enforcing some policies based on
  290.    various preferences and constraints.  Policies are determined by the
  291.    AS administration and are provided to BGP in the form of
  292.    configuration information.  These policies are enforced within a BGP
  293.    speaker by affecting the selection of paths from multiple
  294.    alternatives, and by controlling the redistribution of routing
  295.    information.  Policies are not directly encoded in the protocol.
  296.  
  297.    Non-technical constraints are related to political, security, or
  298.    economic considerations.  For example, if an AS is unwilling to carry
  299.    traffic to another AS, it can enforce a policy prohibiting this.  The
  300.    following examples of non-technical constraints can be enforced with
  301.    the use of BGP:
  302.  
  303.       1. A multihomed AS can refuse to act as a transit AS for other
  304.          ASs.  (It does so by not advertising routes to networks other
  305.          than those directly connected to it.)
  306.  
  307.       2. A multihomed AS can become a transit AS by allowing a certain
  308.          set of ASs to use it as such.  (It does so by advertising
  309.          routes to networks to this set of ASs.)
  310.  
  311.       3. An AS can favor or disfavor the use of certain ASs for carrying
  312.          transit traffic from itself to networks advertised with
  313.          competing AS paths.
  314.  
  315.    A number of performance-related criteria can be controlled with the
  316.    use of BGP:
  317.  
  318.       1. An AS can minimize the number of transit ASs.  (Shorter AS
  319.          paths can be preferred over longer ones.)
  320.  
  321.       2. The quality of transit ASs.  If an AS determines, using BGP,
  322.          that two or more AS paths can be used to reach a given
  323.          destination, that AS can use a variety of means to decide which
  324.          of the candidate AS paths it will use.  The quality of an AS
  325.          can be measured by such things as diameter, link speed,
  326.          capacity, tendency to become congested, and quality of
  327.          operation.  Information about these qualities might be
  328.          determined by means other than BGP.
  329.  
  330.       3. Preference of internal routes over external routes.
  331.  
  332.    Non-technical policy will typically override performance issues.
  333.  
  334.    For consistency, combinations of policies and route selection
  335.  
  336.  
  337.  
  338. Interconnectivity Working Group                                 [Page 6]
  339.  
  340. RFC 1164                   BGP - Application                   June 1990
  341.  
  342.  
  343.    procedures that might result in equal cost paths must be resolved in
  344.    a deterministic fashion.
  345.  
  346.    Fundamental to BGP usage is the rule that an AS advertizes to its
  347.    neighboring ASs only those routes that it uses.  This rule reflects
  348.    the "hop-by-hop" routing paradigm generally used by the current
  349.    Internet.  Note that some policies that cannot be supported by the
  350.    "hop-by-hop" routing paradigm and which require such techniques as
  351.    source routing to enforce.  For example, BGP does not enable one AS
  352.    to send traffic to a neighbor AS intending that that traffic take a
  353.    different route from that taken by traffic originating in the
  354.    neighbor AS.  On the other hand, BGP can support any policy
  355.    conforming to the "hop-by-hop" routing paradigm.  Since the current
  356.    Internet uses only the "hop-by-hop" routing paradigm and since BGP
  357.    can support any policy that conforms to that paradigm, BGP is highly
  358.    applicable as an inter-AS routing protocol for the current Internet.
  359.  
  360. 4. Operational Issues
  361.  
  362. 4.1 Path Selection
  363.  
  364.    One of the major tasks of a BGP speaker for a given AS at a given
  365.    connection is to evaluate different paths to a destination network
  366.    from its border gateways at that connection, select the best one, and
  367.    then advertise it to all of its BGP neighbors at that same connection
  368.    (subject to policy constraints).  The key issue is how different
  369.    paths are evaluated and compared.
  370.  
  371.    In traditional distance vector protocols (e.g., RIP) there is only
  372.    one metric (e.g., hop count) associated with a path.  As such,
  373.    comparison of different paths is reduced to simply comparing two
  374.    numbers.  A complication in Inter-AS routing arises from the lack of
  375.    a universally agreed-upon metric among ASs that can be used to
  376.    evaluate external paths.  Rather, each AS may have its own set of
  377.    criteria for path evaluation.
  378.  
  379.    A BGP speaker within an Autonomous System builds a routing database
  380.    consisting of the set of all feasible paths and the list of networks
  381.    reachable through each path.  In an efficient implementation, it will
  382.    be important to store and process these paths and bundle the networks
  383.    reachable through them.  For purposes of precise discussion, however,
  384.    it's useful to consider the set of feasible paths for a given
  385.    destination network.  In most cases, we would expect to find only one
  386.    feasible path in the set.  This will often, however, not be the case.
  387.    All feasible paths must be maintained, and their maintenance speeds
  388.    adaptation to the loss of the primary path, but only the primary path
  389.    at any given time will ever be advertised.
  390.  
  391.  
  392.  
  393.  
  394. Interconnectivity Working Group                                 [Page 7]
  395.  
  396. RFC 1164                   BGP - Application                   June 1990
  397.  
  398.  
  399.    The path selection process can be formalized by defining a partial
  400.    order over the set of all possible paths to a given destination
  401.    network.  One way to define this partial order is to define a
  402.    function that maps each full AS path to a non-negative integer that
  403.    denotes the path's degree of preference.  Path selection is then
  404.    reduced to applying this function to all feasible paths and choosing
  405.    the one with the highest degree of preference.
  406.  
  407.    In actual BGP implementations, criteria for assigning degree of
  408.    preferences to a path can be specified in a configuration file.
  409.  
  410.    The process of assigning a degree of preference to a path can be
  411.    based on several sources of information:
  412.  
  413.       1. Information explicitly present in the full AS path.
  414.  
  415.       2. A combination of information that can be derived from the full
  416.          AS path and information outside the scope of BGP.
  417.  
  418.    The criteria used to assign a degree of preference to a path can be
  419.    classified as primitive or compound.  Possible primitive criteria
  420.    include:
  421.  
  422.       -  AS count.  Paths with a smaller AS count are generally better.
  423.  
  424.       -  Presence or absence of a certain AS or ASs in the path.  By
  425.          means of information outside the scope of BGP, an AS may know
  426.          some performance characteristics (e.g., bandwidth, MTU, intra-
  427.          AS diameter) of certain ASs and may try to avoid or prefer
  428.          them.
  429.  
  430.       -  Path origin.  A path whose endpoint is internal to the last AS
  431.          on the path (BGP is used over the entire path) is generally
  432.          better than one for which part of the path was learned via EGP
  433.          or some other means.
  434.  
  435.       -  AS path subsets.  An AS path that is a subset of a longer AS
  436.          path to the same destination should be preferred over the
  437.          longer path.  Any problem in the shorter path (such as an
  438.          outage) will also be a problem in the longer path.
  439.  
  440.       -  Link dynamics.  Stable paths should be preferred over unstable
  441.          ones.  Note that this criterion must be used in a very careful
  442.          way to avoid causing unnecessary route fluctuation.  Generally,
  443.          any criteria that depend on dynamic information might cause
  444.          routing instability and should be treated very carefully.
  445.  
  446.       -  Policy consideration.  BGP supports policy based routing based
  447.  
  448.  
  449.  
  450. Interconnectivity Working Group                                 [Page 8]
  451.  
  452. RFC 1164                   BGP - Application                   June 1990
  453.  
  454.  
  455.          on the policy based distribution of routing information defined
  456.          in RFC 1104 [2].  A BGP gateway may be aware of some policy
  457.          constraints (both within and outside of its own AS) and do
  458.          appropriate path selection.  Paths that do not comply with
  459.          policy requirements are not considered further.
  460.  
  461.    Metrics based on compound criteria can be computed as a weighted
  462.    combination of the degree of preferences of primitive criteria.  The
  463.    use of compound criteria should be done with extreme caution since it
  464.    involves comparing potentially uncomparable quantities.
  465.  
  466. 4.2 Syntax and Semantics for BGP Configuration Files
  467.  
  468.    A major task in using BGP is thus to assign a degree of preference to
  469.    each available AS-path.  This degree of preference will generally be
  470.    a function of the number of ASs in the path, properties of the
  471.    specific ASs in the path, the origin of the route, and properties of
  472.    the specific border router to be used in the first hop.  In this
  473.    section we consider how a network administrator might articulate this
  474.    function by means of a configuration file.  In the future, we can
  475.    imagine using tools based on network management protocols such as
  476.    SNMP for this task, but the protocols do not currently support this
  477.    ability.
  478.  
  479.    In addition to controlling the selection of the best path to a given
  480.    network, the network administrator must control the advertisement of
  481.    this best path to neighboring ASs.  Therefore, path selection and
  482.    path distribution emerge as the two key aspects of policy expression
  483.    in BGP usage.
  484.  
  485.    Since different aspects of one AS's policy interact, and since the
  486.    policies of different ASs interact, it is important to facilitate the
  487.    analysis of such interactions by means of high-quality and consistent
  488.    tools.
  489.  
  490.    There is also a need for tools to translate the expression of the
  491.    network administrator's policy to some technical mechanism within a
  492.    BGP speaker to implement that policy.
  493.  
  494.    These factors suggest that there should be a globally consistent way
  495.    of describing policies in the configuration file.  The syntax and
  496.    semantics of these policies should be capable of expressing the path
  497.    selection phase within the local AS as well as the path
  498.    redistribution phase to other ASs.
  499.  
  500.    Because it may be desirable to coordinate routing policy at an
  501.    external level, it may prove worthwhile to create a language to
  502.    describe this information in a globally consistent way.  Policies
  503.  
  504.  
  505.  
  506. Interconnectivity Working Group                                 [Page 9]
  507.  
  508. RFC 1164                   BGP - Application                   June 1990
  509.  
  510.  
  511.    expressed in such a language could conceivably be used by some high-
  512.    level tools to analyze the interaction among the routing policies of
  513.    different Autonomous Systems.
  514.  
  515.    The following defines one possible syntax and semantics for
  516.    describing AS path policies from the point of view of the local AS.
  517.    Alternative syntaxes with equivalent richness of functionality are
  518.    not precluded.  Other mechanisms may be needed to provide a fully
  519.    functional configuration language.
  520.  
  521.    A complete AS path, supplied by BGP, provides the most important
  522.    mechanism for policy enforcement.  Assigning a degree of preference
  523.    to a particular AS path can be modelled as a matching between this
  524.    path and one or more predefined AS path patterns.  Each predefined AS
  525.    path pattern has a degree of preference that will be assigned to any
  526.    AS path that matches it.
  527.  
  528.    Since patterns are naturally expressed by regular expressions, one
  529.    can use regular expressions over the alphabet of AS numbers to define
  530.    AS path patterns and, therefore, to formulate policies.
  531.  
  532.    Since certain constructs occur frequently in regular expressions, the
  533.    following notational shorthand (operators) is defined:
  534.  
  535.       .  matches any AS number.  To improve readability, "." can be
  536.          replaced by "any" so long as this does not introduce ambiguity.
  537.  
  538.       *  a regular expression followed by * means zero or more
  539.          repetitions
  540.  
  541.       +  a regular expression followed by + means one or more
  542.          repetitions
  543.  
  544.       ?  a regular expression followed by ? means zero or one repetition
  545.  
  546.       |  alternation
  547.  
  548.       () parentheses group subexpressions--an operator, such as * or
  549.          works on a single element or on a regular expression enclosed
  550.          in parentheses
  551.  
  552.       {m,n}  a regular expression followed by {m,n} (where m and n are
  553.          both non-negative integers and m <= n) means at least m and at
  554.          most n repetitions.
  555.  
  556.       {m}  a regular expression followed by {m} (where m is a positive
  557.          integer) means exactly m repetitions.
  558.  
  559.  
  560.  
  561.  
  562. Interconnectivity Working Group                                [Page 10]
  563.  
  564. RFC 1164                   BGP - Application                   June 1990
  565.  
  566.  
  567.       {m,} a regular expression followed by {m,} (where m is a positive
  568.          integer) means m or more repetitions.
  569.  
  570. Any regular expression is generated by these rules.
  571.  
  572. The Policy Based Routing Language can then be defined as follows:
  573.  
  574.       <Policy-Based-Routing> ::= { <policy-statement> }
  575.  
  576.       Semantics: each policy statement might cause a given possible BGP
  577.       advertisement (possibility) to be installed into the routing table
  578.       as the route to a given (set of) networks.  Thus, an empty
  579.       Policy-Based-Routing means that no possibilities will be accepted.
  580.  
  581.       <policy-statement> ::=
  582.                   <policy-expression> '=' <dop-expression> ';'
  583.  
  584.       Semantics: if a given possibility matches the policy-expression,
  585.       then that possibility will be accepted with a degree of preference
  586.       denoted by the integer value dop-expression.
  587.  
  588.       <policy-expression> ::=
  589.               <policy-term> |
  590.               <policy-term> <policy-operator> <policy-term>
  591.  
  592.       <policy-term> ::=
  593.               <network-list> <AS-path> <origin> <distribution-list> |
  594.               '(' <policy-expression> ')' |
  595.               NOT <policy-expression> |
  596.               <>
  597.  
  598.       <policy-operator> ::= OR | AND
  599.  
  600.       Semantics: the intersection of the network list of a possibility
  601.       and the network-list must be non-empty; the AS-path of the
  602.       possibility must match the AS-path as a sequence; the origin of
  603.       the possibility must be a member of the origin set; if these
  604.       conditions are met, the route denoted by the possibility is
  605.       accepted as a possible route to those networks of the intersection
  606.       of the possibility network list and the network-list.
  607.  
  608.       <AS-path> ::= "regular expression over AS numbers"
  609.  
  610.       Semantics: the AS-path of the possibility must be generated by the
  611.       regular expression <AS-path>.
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618. Interconnectivity Working Group                                [Page 11]
  619.  
  620. RFC 1164                   BGP - Application                   June 1990
  621.  
  622.  
  623.       <network-list> ::= '<' { network network-list } '>' |
  624.                          '<' ANY '>'
  625.  
  626.       Semantics: A non-empty sequence enumerates the network numbers of
  627.       the network-list; ANY denotes the set of all network numbers.
  628.  
  629.       <origin> ::= IGP | EGP | INCOMPLETE | ANY
  630.  
  631.       Semantics: origin enumerates the sequence of acceptable origins;
  632.       ANY denotes the set of all origins.
  633.  
  634.       <distribution-list> ::= '<' { AS } '>' |
  635.                               '<' ANY '>'
  636.  
  637.       Semantics: if a given possibility as accepted and installed into
  638.       the routing table, then distribution-list is the set of
  639.       (neighboring) autonomous systems to whose border routers we will
  640.       distribute the BGP-derived routes.
  641.  
  642.       <dop-expression> ::= <dop-term> |
  643.                            <dop-term> '+' <dop-term> |
  644.                            <dop-term> '-' <dop-term> |
  645.                            <dop-term> '*' <dop-term> |
  646.                            <dop-term> '/' <dop-term> |
  647.                            REJECT
  648.  
  649.       <dop-term> ::= <integer> |
  650.                      <function> |
  651.                      '(' <dop-expression> ')'
  652.  
  653.       Semantics: if a possibility matches with degree of preference
  654.       REJECT, then that possibility will not be used.  Otherwise, the
  655.       integer value of the degree of preference indicates the degree of
  656.       preference of the possibility, with higher values preferred over
  657.       lower ones.
  658.  
  659.    White spaces can be used between symbols to improve readability.
  660.    "<>" denotes the empty sequence.
  661.  
  662.    There are two built-in functions, PathLength() and PathWeight().
  663.    PathLength() takes the AS path as an argument and returns the number
  664.    of ASs in that path.  PathWeight() takes the AS path and an AS weight
  665.    table as arguments and returns the sum of weights of the ASs in the
  666.    AS path as defined by the AS weight table.  In order to preserve
  667.    determinism, the AS weight table must always have a default weight
  668.    which will be assigned to any AS which is not in that table.
  669.  
  670.    The AS path, as used above, is constructed from right to left which
  671.  
  672.  
  673.  
  674. Interconnectivity Working Group                                [Page 12]
  675.  
  676. RFC 1164                   BGP - Application                   June 1990
  677.  
  678.  
  679.    is consistent with BGP), so that the most recent AS in the path
  680.    occupies the leftmost position.
  681.  
  682.    Each network (and its associated complete AS path) received from
  683.    other BGP neighbors is matched against local Routing Policies.
  684.  
  685.    If either no match occurs or the degree of preference associated with
  686.    the matched policy is REJECT, then the received information is
  687.    rejected.  Otherwise, a degree of preference associated with the
  688.    matched policy is assigned to that path.  Notice that the process
  689.    terminates on the first successful match.  Therefore, policy-terms
  690.    should be ordered from more specific to more general.
  691.  
  692.    The semantics of a matched policy is as follows:  If a network in
  693.    <network-list> that was originally introduced into BGP from <origin>
  694.    is received via <AS-path>, that network should be redistributed to
  695.    all ASs in <distribution-list>.
  696.  
  697.    The following examples (some taken from RFC 1102 [3]) illustrate how
  698.    Policy Terms can be written.
  699.  
  700.    In the following topology, H elements are hosts, G elements are
  701.    Policy Gateways running BGP, and numbered elements are ASs.
  702.  
  703.         H1 --- 1 -G12...G21 - 2 -- G23...G32 -- 3 ----- H2
  704.                |                                |
  705.                |                                |
  706.                |                                |
  707.                |- G14...G41 - 4 -- G43...G34 ---|- G35...G53 - 5
  708.                               |                                |
  709.                               |                                |
  710.                               |                               H4
  711.                               H3
  712.  
  713.    In this picture, there are four hosts, ten gateways, and five
  714.    Autonomous Systems.  Gateways G12 and G14 belong to AS 1.  Gateways
  715.    G21 and G23 belong to AS 2.  Gateways G41 and G43 belongs to AS 4.
  716.    Gateways G32, G34, and G35 belong to AS 3.  Gateway G53 belongs to AS
  717.    5.  Dashed lines denote intra-AS connections.  Dotted lines denote
  718.    inter-AS connections.
  719.  
  720.    First, consider AS 2.  It has no hosts attached, and models a transit
  721.    service, such as the NSFNET backbone network.  It may have a very
  722.    simple policy: it will carry any traffic between any two ASs, without
  723.    further constraint.  If AS 1 and AS 3 are neighboring domains, then
  724.    its policy term could be written as:
  725.  
  726.       AS 2: < ANY > < (1 | 3) .* > < IGP > < 1 3 > = 10
  727.  
  728.  
  729.  
  730. Interconnectivity Working Group                                [Page 13]
  731.  
  732. RFC 1164                   BGP - Application                   June 1990
  733.  
  734.  
  735.    The first component in this policy, the network list
  736.  
  737.       < ANY >
  738.  
  739.    says that any network is subject to this policy.  The second
  740.    component, the AS path
  741.  
  742.       < (1 | 3) .* >
  743.  
  744.    says that routing information that came from either AS 1 or AS 3
  745.    matches this policy, including routes from ASs that lie beyond AS 1
  746.    and AS 3.  The third component, the origin
  747.  
  748.       < IGP >
  749.  
  750.    says that this route must be interior with respect to the originating
  751.    AS, implying that routes imported via EGP or some other mechanism
  752.    would not match this policy.  The fourth component, the distribution
  753.    list
  754.  
  755.       < 1  3 >
  756.  
  757.    says that this route may be redistributed to both AS 1 and AS 3.
  758.    Finally, the degree of preference assigned to any route which matches
  759.    this policy is set to 10.
  760.  
  761.    To improve readability, the above policy can be rewritten as:
  762.  
  763.       AS 2: < ANY > < (1 | 3) ANY* > < IGP > < 1  3 > = 10
  764.  
  765.    Next, consider AS 3.  It is willing to provide transit service to AS
  766.    4 and AS 5, presumably due to multilateral agreements.  AS 3 should
  767.    set its policy as follows:
  768.  
  769.       AS 3: < ANY > < (4 | 5) > < IGP > < 2  4  5 > = 10
  770.       AS 3: < ANY > < 2  .* > < ANY > < 4  5 > = 10
  771.       AS 3: < ANY > < 3 > < ANY > < 2  4  5 > = 10
  772.  
  773.    This would allow AS 3 to distribute internal routes received from ASs
  774.    4 and 5 to ASs 2, 4, and 5, and all backbone routes through AS 2
  775.    would be distributed to ASs 4 and 5.  AS 3 would advertise its own
  776.    networks to ASs 2, 4, and 5.  Hosts in AS 4 and AS 5 would be able to
  777.    reach each other, as well as hosts in ASs 1 and 3 and anything beyond
  778.    them.  AS 3 allows any origin in routes from AS 2.  This implies that
  779.    AS 3 trusts AS 2 to impose policy on routes imported by means other
  780.    than BGP.  Note that although the policy statement would appear to
  781.    allow AS 3 to send ASs 4 and 5 their own routes, the BGP protocol
  782.    would detect this as a routing loop and prevent it.
  783.  
  784.  
  785.  
  786. Interconnectivity Working Group                                [Page 14]
  787.  
  788. RFC 1164                   BGP - Application                   June 1990
  789.  
  790.  
  791.    Now consider AS 1.  AS 1 wishes to use the backbone service provided
  792.    by AS 2, and is willing to carry transit traffic for AS 4.  The
  793.    policy statements for AS 1 might read:
  794.  
  795.       AS 1: < ANY > < 4 > < IGP > < 2 > = 150
  796.       AS 1: < ANY > < 2  .* > < ANY > < 4 > = 150
  797.       AS 1: < ANY > < 1 > < ANY > < 2  4 > = 150
  798.  
  799.    AS 1 will redistribute all routes learned from the AS 2 backbone to
  800.    AS 4, and vice versa, and distribute routes to its own networks to
  801.    both AS 2 and AS 4.  The degree of preference assigned to any route
  802.    which matches this policy is set to 150.
  803.  
  804.    AS 5 is a more interesting case.  AS 5 wishes to use the backbone
  805.    service, but is not directly connected to AS 2.  Its policy
  806.    statements could be as follows:
  807.  
  808.       AS 5: < ANY > < 3  4 > < IGP > < > = 10
  809.       AS 5: < ANY > < 3  2  .* > < . > < > = 10
  810.       AS 5: < ANY > < 5 > < . > < 3 > = 10
  811.  
  812.    This policy imports routes through AS 2 and AS 3 into AS 5, and
  813.    allows AS 5 and AS 4 to communicate through AS 3.  Since AS 5 does
  814.    not redistribute any routes other than its own, it is a stub AS.
  815.    Note that AS 5 does not trust AS 3 to advertise only routes through
  816.    AS 2, and thus applies its own filter to ensure that it only uses the
  817.    backbone.  This lack of trust makes it necessary to add the second
  818.    policy term.
  819.  
  820.    AS 4 is a good example of a multihomed AS.  AS 4 wishes to use AS 3
  821.    as is primary path to the backbone, with AS 1 as a backup.
  822.    Furthermore, AS 4 does not wish to provide any transit service
  823.    between ASs 1 and 3.  Its policy statement could read:
  824.  
  825.       AS 4: < ANY > < 3  .* > < ANY > < > = 10
  826.       AS 4: < ANY > < 1  .* > < ANY > < > = 20
  827.       AS 4: < ANY > < 4 > < ANY > < 1  3 > = 10
  828.  
  829.    Paths to any network through AS 3 are preferred, but AS 1 will be
  830.    used as a backup if necessary.  Note that since AS 4 trusts AS 3 to
  831.    provide it with reasonable routes, it is not necessary to explicitly
  832.    import routes from AS 5.  Since the redistribution terms are null
  833.    except for networks within AS 4, AS 4 will never carry any transit
  834.    traffic.
  835.  
  836.    Given the topology and policies described above, it becomes apparent
  837.    that two paths of equal preference would be available from AS 2 to
  838.    any of the networks in AS 4.  Since ties are not allowed, an
  839.  
  840.  
  841.  
  842. Interconnectivity Working Group                                [Page 15]
  843.  
  844. RFC 1164                   BGP - Application                   June 1990
  845.  
  846.  
  847.    arbitrary tie-breaking mechanism would come into play (as described
  848.    above), which might result in less than optimal routes to some
  849.    networks.  An alternative mechanism that would provide optimal routes
  850.    while still allowing fallback paths would be to provide network-by-
  851.    network policies in specific cases, and explicit tie-breaking
  852.    policies for the remaining networks.  For example, the policies for
  853.    AS 2 could be rewritten as follows:
  854.  
  855.       AS 2: < 35 > < 1  .* > < IGP > < 3 > = 10
  856.       AS 2: < 35 > < 3  .* > < IGP > < 1 > = 20
  857.       AS 2: < ANY > < 1  .* > < IGP > < 3 > = 20
  858.       AS 2: < ANY > < 3  .* > < IGP > < 1 > = 10
  859.  
  860.    Paths to network 35 through AS 1 would be preferred, with AS 3 as a
  861.    fallback; paths to all other networks through AS 3 would be preferred
  862.    over those through AS 1.  Such optimizations may become arbitrarily
  863.    complex.
  864.  
  865.    There may be other, simpler ways to assign a degree of preference to
  866.    an AS path.
  867.  
  868.    The simplest way to assign a degree of preference to a particular
  869.    path is to use the number of ASs in the AS path as the degree of
  870.    preference.  This approach reflects the heuristic that shorter paths
  871.    are usually better than longer ones.  This policy can be implemented
  872.    by using the PathLength() built-in function in the following policy
  873.    statement:
  874.  
  875.       < ANY > < .* > < ANY > < ANY > = PathLength(ASpath)
  876.  
  877.    This policy assigns to any network with an arbitrary AS path a degree
  878.    of preference equal to the number of ASs in the AS path; it then
  879.    redistributes this information to all other BGP speakers. As an
  880.    example, an AS path which traverses three different Autonomous
  881.    Systems will be assigned the degree of preference 3.
  882.  
  883.    Another approach is to assign a certain degree of preference to each
  884.    individual AS, and then determine the degree of preference of a
  885.    particular AS path as the sum of the degree of preferences of the ASs
  886.    in that path.  Note that this approach does not require the
  887.    assignment of a specific degree of preference to every AS in the
  888.    Internet.  For ASs with an unknown degree of preference, a default
  889.    can be used.  This policy can be implemented by using the
  890.    PathWeight() built-in function in the following policy statement:
  891.  
  892.       < ANY > < .* > < ANY > < ANY >
  893.                            = PathWeight(ASpath, ASWeightTable)
  894.  
  895.  
  896.  
  897.  
  898. Interconnectivity Working Group                                [Page 16]
  899.  
  900. RFC 1164                   BGP - Application                   June 1990
  901.  
  902.  
  903.    As an example, if Autonomous Systems 145 and 55 have 10 and 15 as
  904.    their weights in the ASWeightTable, and if the default degree of
  905.    preference in the ASWeightTable is 50, then an AS path that traverses
  906.    Autonomous Systems 145, 164, and 55 will be assigned degree of
  907.    preference 75.
  908.  
  909.    The above examples demonstrate some of the simple policies that can
  910.    be implemented with BGP.  In general, very sophisticated policies
  911.    based on partial or complete AS path discrimination can be written
  912.    and enforced.  It should be emphasized that movement toward more
  913.    sophisticated policies will require parallel effort in creating more
  914.    sophisticated tools for policy interaction analysis.
  915.  
  916. 5. The Interaction of BGP and an IGP
  917.  
  918. 5.1 Overview
  919.  
  920.    By definition, all transit ASs must be able to carry traffic external
  921.    to that AS (neither the source nor destination host belongs to the
  922.    AS).  This requires a certain degree of interaction and coordination
  923.    between the Interior Gateway Protocol (IGP) used by that particular
  924.    AS and BGP.  In general, traffic exterior to a given AS is going to
  925.    pass through both interior gateways (gateways that support IGP only)
  926.    and border gateways (gateways that support both IGP and BGP).  All
  927.    interior gateways receive information about external routes from one
  928.    or more of the border gateways of the AS via the IGP.
  929.  
  930.    Depending on the mechanism used to propagate BGP information within a
  931.    given AS, special care must be taken to ensure consistency between
  932.    BGP and the IGP, since changes in state are likely to propagate at
  933.    different rates across the AS.  There may be a time window between
  934.    the moment when some border gateway (A) receives new BGP routing
  935.    information which was originated from another border gateway (B)
  936.    within the same AS, and the moment the IGP within this AS is capable
  937.    of routing transit traffic to that border gateway (B).  During that
  938.    time window, either incorrect routing or "black holes" can occur.
  939.  
  940.    In order to minimize such routing problems, border gateway (A) should
  941.    not advertise a route to some exterior network X to all of its BGP
  942.    neighbors in other ASs until all of the interior gateways within the
  943.    AS are ready to route traffic destined to X via the correct exit
  944.    border gateway (B).  In other words, interior routing should converge
  945.    on the proper exit gateway before advertising routes via that exit
  946.    gateway to other ASs.
  947.  
  948. 5.2 Methods for Achieving Stable Interactions
  949.  
  950.    The following discussion outlines several techniques capable of
  951.  
  952.  
  953.  
  954. Interconnectivity Working Group                                [Page 17]
  955.  
  956. RFC 1164                   BGP - Application                   June 1990
  957.  
  958.  
  959.    achieving stable interactions between BGP and the IGP within an
  960.    Autonomous System.
  961.  
  962. 5.2.1 Propagation of BGP Information via the IGP
  963.  
  964.    While BGP can provide its own mechanism for carrying BGP information
  965.    within an AS, one can also use an IGP to transport this information,
  966.    as long as the IGP supports complete flooding of routing information
  967.    (providing the mechanism to distribute the BGP information) and one-
  968.    pass convergence (making the mechanism effectively atomic).  If an
  969.    IGP is used to carry BGP information, then the period of
  970.    desynchronization described earlier does not occur at all, since BGP
  971.    information propagates within the AS synchronously with the IGP, and
  972.    the IGP converges more or less simultaneously with the arrival of the
  973.    new routing information.  Note that the IGP only carries BGP
  974.    information and should not interpret or process this information.
  975.  
  976. 5.2.2 Tagged Interior Gateway Protocol
  977.  
  978.    Certain IGPs can tag routes exterior to an AS with the identity of
  979.    their exit points while propagating them within the AS.  Each border
  980.    gateway should use identical tags for announcing exterior routing
  981.    information (received via BGP) both into the IGP and into Internal
  982.    BGP when propagating this information to other border gateways within
  983.    the same AS.  Tags generated by a border gateway must uniquely
  984.    identify that particular border gateway--different border gateways
  985.    must use different tags.
  986.  
  987.    All Border Gateways within a single AS must observe the following two
  988.    rules:
  989.  
  990.    1. Information received via Internal BGP by a border gateway A
  991.       declaring a network to be unreachable must immediately be
  992.       propagated to all of the External BGP neighbors of A.
  993.  
  994.    2. Information received via Internal BGP by a border gateway A about
  995.       a reachable network X cannot be propagated to any of the External
  996.       BGP neighbors of A unless/until A has an IGP route to X and both
  997.       the IGP and the BGP routing information have identical tags.
  998.  
  999.    These rules guarantee that no routing information is announced
  1000.    externally unless the IGP is capable of correctly supporting it.  It
  1001.    also avoids some causes of "black holes".
  1002.  
  1003.    One possible method for tagging BGP and IGP routes within an AS is to
  1004.    use the IP address of the exit border gateway announcing the exterior
  1005.    route into the AS.  In this case the "gateway" field in the BGP
  1006.    UPDATE message is used as the tag.
  1007.  
  1008.  
  1009.  
  1010. Interconnectivity Working Group                                [Page 18]
  1011.  
  1012. RFC 1164                   BGP - Application                   June 1990
  1013.  
  1014.  
  1015. 5.2.3 Encapsulation
  1016.  
  1017.    Encapsulation provides the simplest (in terms of the interaction
  1018.    between the IGP and BGP) mechanism for carrying transit traffic
  1019.    across the AS.  In this approach, transit traffic is encapsulated
  1020.    within an IP datagram addressed to the exit gateway.  The only
  1021.    requirement imposed on the IGP by this approach is that it should be
  1022.    capable of supporting routing between border gateways within the same
  1023.    AS.
  1024.  
  1025.    The address of the exit gateway A for some exterior network X is
  1026.    specified in the "gateway" field of the BGP UPDATE message received
  1027.    from gateway A via Internal BGP by all other border gateways within
  1028.    the same AS.  In order to route traffic to network X, each border
  1029.    gateway within the AS encapsulates it in datagrams addressed to
  1030.    gateway A.  Gateway A then performs decapsulation and forwards the
  1031.    original packet to the proper gateway in another AS.
  1032.  
  1033.    Since encapsulation does not rely on the IGP to carry exterior
  1034.    routing information, no synchronization between BGP and the IGP is
  1035.    required.
  1036.  
  1037.    Some means of identifying datagrams containing encapsulated IP, such
  1038.    as an IP protocol type code, must be defined if this method is to be
  1039.    used.
  1040.  
  1041.    Note, that if a packet to be encapsulated has length that is very
  1042.    close to the MTU, that packet would be fragmented at the gateway that
  1043.    performs encapsulation.
  1044.  
  1045. 5.2.4 Other Cases
  1046.  
  1047.    There may be ASs with IGPs which can neither carry BGP information
  1048.    nor tag exterior routes (e.g., RIP).  In addition, encapsulation may
  1049.    be either infeasible or undesirable.  In such situations, the
  1050.    following two rules must be observed:
  1051.  
  1052.    1. Information received via Internal BGP by a border gateway A
  1053.       declaring a network to be unreachable must immediately be
  1054.       propagated to all of the External BGP neighbors of A.
  1055.  
  1056.    2. Information received via Internal BGP by a border gateway A about
  1057.       a reachable network X cannot be propagated to any of the External
  1058.       BGP neighbors of A unless A has an IGP route to X and sufficient
  1059.       time (holddown) has passed for the IGP routes to have converged.
  1060.  
  1061.    The above rules present necessary (but not sufficient) conditions for
  1062.    propagating BGP routing information to other ASs.  In contrast to
  1063.  
  1064.  
  1065.  
  1066. Interconnectivity Working Group                                [Page 19]
  1067.  
  1068. RFC 1164                   BGP - Application                   June 1990
  1069.  
  1070.  
  1071.    tagged IGPs, these rules cannot ensure that interior routes to the
  1072.    proper exit gateways are in place before propagating the routes to
  1073.    other ASs.
  1074.  
  1075.    If the convergence time of an IGP is less than some small value X,
  1076.    then the time window during which the IGP and BGP are unsynchronized
  1077.    is less than X as well, and the whole issue can be ignored at the
  1078.    cost of transient periods (of less than length X) of routing
  1079.    instability.  A reasonable value for X is a matter for further study,
  1080.    but X should probably be less than one second.
  1081.  
  1082.    If the convergence time of an IGP cannot be ignored, a different
  1083.    approach is needed.  Mechanisms and techniques which might be
  1084.    appropriate in this situation are subjects for further study.
  1085.  
  1086. 6. Implementation Recommendations
  1087.  
  1088. 6.1 Multiple Networks Per Message
  1089.  
  1090.    The BGP protocol allows for multiple networks with the same AS path
  1091.    and next-hop gateway to be specified in one message.  Making use of
  1092.    this capability is highly recommended.  With one network per message
  1093.    there is a substantial increase in overhead in the receiver.  Not
  1094.    only does the system overhead increase due to the reception of
  1095.    multiple messages, but the overhead of scanning the routing table for
  1096.    flash updates to BGP peers and other routing protocols (and sending
  1097.    the associated messages) is incurred multiple times as well.  One
  1098.    method of building messages containing many networks per AS path and
  1099.    gateway from a routing table that is not organized per AS path is to
  1100.    build many messages as the routing table is scanned.  As each network
  1101.    is processed, a message for the associated AS path and gateway is
  1102.    allocated, if it does not exist, and the new network is added to it.
  1103.    If such a message exists, the new network is just appended to it.  If
  1104.    the message lacks the space to hold the new network, it is
  1105.    transmitted, a new message is allocated, and the new network is
  1106.    inserted into the new message.  When the entire routing table has
  1107.    been scanned, all allocated messages are sent and their resources
  1108.    released.  Maximum compression is achieved when all networks share a
  1109.    gateway and common path attributes, making it possible to send many
  1110.    networks in one 4096-byte message.
  1111.  
  1112. 6.2 Preventing Excessive Resource Utilization
  1113.  
  1114.    When peering with a BGP implementation that does not compress
  1115.    multiple networks into one message, it may be necessary to take steps
  1116.    to reduce the overhead from the flood of data received when a peer is
  1117.    acquired or a significant network topology change occurs.  One method
  1118.    of doing this is to rate limit flash updates.  This will eliminate
  1119.  
  1120.  
  1121.  
  1122. Interconnectivity Working Group                                [Page 20]
  1123.  
  1124. RFC 1164                   BGP - Application                   June 1990
  1125.  
  1126.  
  1127.    the redundant scanning of the routing table to provide flash updates
  1128.    for BGP peers and other routing protocols.  A disadvantage of this
  1129.    approach is that it increases the propagation latency of routing
  1130.    information.  By choosing a minimum flash update interval that is not
  1131.    much greater than the time it takes to process the multiple messages,
  1132.    this latency should be minimized.
  1133.  
  1134. 6.3 Processing Messages on a Stream Protocol
  1135.  
  1136.    Due to the stream nature of TCP, all the data for received messages
  1137.    does not necessarily arrive at the same time, due to the nature of
  1138.    TCP.  This can make it difficult to process the data as messages,
  1139.    especially on systems such as BSD Unix where it is not possible to
  1140.    determine how much data has been received but not yet processed.  One
  1141.    method that can be used in this situation is to first try to read
  1142.    just the message header.  For the KeepAlive message type, this is a
  1143.    complete message; for other message types, the header should first be
  1144.    verified, in particular the total length.  If all checks are
  1145.    successful, the specified length, minus the size of the message
  1146.    header is the amount of data left to read.  An implementation that
  1147.    would "hang" the routing information process while trying to read
  1148.    from a peer could set up a message buffer (1024 bytes) per peer and
  1149.    fill it with data as available until a complete message has been
  1150.    received.
  1151.  
  1152. 6.4 Processing Update Messages
  1153.  
  1154.    In BGP, all Update messages are incremental.  Once a particular
  1155.    network is listed in an Update message as being reachable through an
  1156.    AS path and gateway, that piece of information is expected to be
  1157.    retained indefinitely.  In order for a route to a network to be
  1158.    removed, it must be explicitly listed in an Update message as being
  1159.    unreachable or with new routing information to replace the old.  Note
  1160.    that a BGP peer will only advertise one route to a given network, so
  1161.    any announcement of that network by a particular peer replaces any
  1162.    previous information about that network received from the same peer.
  1163.  
  1164.    This approach has the obvious advantage of low overhead; if all
  1165.    routes are stable, only KeepAlive messages will be sent.  There is no
  1166.    periodic flood of route information.
  1167.  
  1168.    However, this means that a consistent view of routing information
  1169.    between BGP peers is only possible over the course of a single
  1170.    transport connection, since there is no mechanism for a complete
  1171.    update.  This requirement is accommodated by specifying that BGP
  1172.    peers must transition to the Idle state upon the failure of a
  1173.    transport connection.
  1174.  
  1175.  
  1176.  
  1177.  
  1178. Interconnectivity Working Group                                [Page 21]
  1179.  
  1180. RFC 1164                   BGP - Application                   June 1990
  1181.  
  1182.  
  1183. 7. Conclusion
  1184.  
  1185.    The BGP protocol provides a high degree of control and flexibility
  1186.    for doing interdomain routing while enforcing policy and performance
  1187.    constraints and avoiding routing loops.  It is hoped that the
  1188.    guidelines presented here will provide a starting point for more
  1189.    sophisticated and manageable routing in the Internet as it grows.
  1190.  
  1191. References
  1192.  
  1193.    [1]  Lougheed, K. and Y. Rekhter, "A Border Gateway Protocol", RFC
  1194.         1163, cisco Systems and IBM Watson Research Center, June 1990.
  1195.  
  1196.    [2]  Braun, H-W., "Models of Policy Based Routing", RFC 1104,
  1197.         Merit/NSFNET, June 1989.
  1198.  
  1199.    [3]  Clark, D., "Policy Routing in Internet Protocols", RFC 1102,
  1200.         M.I.T., May 1989.
  1201.  
  1202. Security Considerations
  1203.  
  1204.    Security issues are not discussed in this memo.
  1205.  
  1206. Authors' Addresses
  1207.  
  1208.    Jeffrey C. Honig
  1209.    Theory Center
  1210.    265 Olin Hall
  1211.    Cornell University
  1212.    Ithaca, NY  14853-5201
  1213.  
  1214.    Phone:  (607) 255-8686
  1215.  
  1216.    Email:  JCH@TCGOULD.TN.CORNELL.EDU
  1217.  
  1218.  
  1219.    Dave Katz
  1220.    Merit/NSFNET
  1221.    1075 Beal Ave.
  1222.    Ann Arbor, MI  48109
  1223.  
  1224.    Phone:  (313) 763-4898
  1225.  
  1226.    Email:  DKATZ@MERIT.EDU
  1227.  
  1228.  
  1229.  
  1230.  
  1231.  
  1232.  
  1233.  
  1234. Interconnectivity Working Group                                [Page 22]
  1235.  
  1236. RFC 1164                   BGP - Application                   June 1990
  1237.  
  1238.  
  1239.    Matt Mathis
  1240.    Pittsburgh Supercomputing Center
  1241.    4400 Fifth Ave.
  1242.    Pittsburgh, PA  15213
  1243.  
  1244.    Phone:  (412) 268-3319
  1245.  
  1246.    Email:  MATHIS@FARADAY.ECE.CMU.EDU
  1247.  
  1248.  
  1249.    Yakov Rekhter
  1250.    T.J. Watson Research Center
  1251.    IBM Corporation
  1252.    P.O. Box 218
  1253.    Yorktown Heights, NY  10598
  1254.  
  1255.    Phone:  (914) 945-3896
  1256.  
  1257.    Email:  YAKOV@IBM.COM
  1258.  
  1259.  
  1260.    Jie Yun (Jessica) Yu
  1261.    Merit/NSFNET
  1262.    1075 Beal Ave.
  1263.    Ann Arbor, MI  48109
  1264.  
  1265.    Phone:  (313) 936-3000
  1266.  
  1267.    Email:  JYY@MERIT.EDU
  1268.  
  1269.  
  1270.  
  1271.  
  1272.  
  1273.  
  1274.  
  1275.  
  1276.  
  1277.  
  1278.  
  1279.  
  1280.  
  1281.  
  1282.  
  1283.  
  1284.  
  1285.  
  1286.  
  1287.  
  1288.  
  1289.  
  1290. Interconnectivity Working Group                                [Page 23]
  1291.